Efficient Multiplication of Varying-Length #s [Conceptual]
Posted
by
Milan Patel
on Stack Overflow
See other posts from Stack Overflow
or by Milan Patel
Published on 2012-03-24T23:16:55Z
Indexed on
2012/03/24
23:29 UTC
Read the original article
Hit count: 211
Write the pseudocode of an algorithm that takes in two arbitrary length numbers (provided as strings), and computes the product of these numbers. Use an efficient procedure for multiplication of large numbers of arbitrary length. Analyze the efficiency of your algorithm.
I decided to take the (semi) easy way out and use the Russian Peasant Algorithm. It works like this:
a * b = a/2 * 2b if a is even
a * b = (a-1)/2 * 2b + a if a is odd
My pseudocode is:
rpa(x, y){
if x is 1
return y
if x is even
return rpa(x/2, 2y)
if x is odd
return rpa((x-1)/2, 2y) + y
}
I have 3 questions:
- Is this efficient for arbitrary length numbers? I implemented it in C and tried varying length numbers. The run-time in was near-instant in all cases so it's hard to tell empirically...
- Can I apply the Master's Theorem to understand the complexity...?
- a = # subproblems in recursion = 1 (max 1 recursive call across all states)
- n / b = size of each subproblem = n / 1 -> b = 1 (problem doesn't change size...?)
- f(n^d) = work done outside recursive calls = 1 -> d = 0 (the addition when a is odd)
- a = 1, b^d = 1, a = b^d -> complexity is in n^d*log(n) = log(n)
- this makes sense logically since we are halving the problem at each step, right?
- What might my professor mean by providing arbitrary length numbers "as strings". Why do that?
Many thanks in advance
© Stack Overflow or respective owner